/*
 * =====================================================================================
 *
 *       Filename:  main.cpp
 *
 *    Description:
 *
 *        Version:  1.0
 *        Created:  2017年08月10日 09时47分00秒
 *       Revision:  none
 *       Compiler:  gcc
 *
 *         Author:  Crane (), wanghe@galaxyeye-tech.com
 *   Organization:  Galaxy-eye
 *
 * =====================================================================================
 */

#include <iostream>
#include <vector>

struct Record
{
    // sum[from, max] == max;
    int from;
    int to;
    int max;

    Record(int f, int t, int m)
    {
        SetAll(f, t, m);
    }

    int GetFrom() const { return from; }

    void SetFrom(int f) { from = f;    }

    int GetTo() const   { return to;   }

    void SetTo(int t)   { to = t;      }
    void SetInterval(int f, int t)
    {
        from = f;
        to  = t;
    }

    void SetAll(int f, int t, int m)
    {
        SetFrom(f);
        SetTo(t);
        SetMax(m);
    }

    int GetMax() const  { return max;  }

    void SetMax(int m)  { max = m;     }

    void show() const {
        /*
         *std::cout << "from index: " << from << std::endl;
         *std::cout << "to   index: " << to   << std::endl;
         */
        std::cout << "[" << from <<", " << to <<  "]";
        std::cout << ": max sum : " << max  << std::endl;
        std::cout << std::endl;
    }

    template<class Cont>
    void show(const Cont &nums) const {
        /*
         *std::cout << "from index: " << from << std::endl;
         *std::cout << "to   index: " << to   << std::endl;
         */
        std::cout << "[" << from <<", " << to <<  "]" << std::endl;

        for (int i = from; i <= to; i++)
        {
            std::cout << nums[i] << ", ";
        }
        std::cout << std::endl;

        std::cout << ": max sum : " << max  << std::endl;
        std::cout << std::endl;
    }
};

// [first, last)
template<class Iterator>
int MaxArray(Iterator first, Iterator last)
{
    std::vector<int>  nums;
    nums.reserve(15);
    std::copy(first, last, std::back_inserter(nums));

    Record  maxRecord(0, 0, nums[0]);
    Record  curRecord(0, 0, nums[0]);

    // 只遍历一次
    // 复杂度O(n)
    for (size_t i = 1; i < nums.size(); i++)
    {
        int add = curRecord.GetMax() + nums[i];

        if (add > nums[i]) {
            curRecord.SetAll( curRecord.GetFrom(), i, add);
        } else {
            curRecord.SetAll(i, i, nums[i]);
        }

        if ( curRecord.GetMax() > maxRecord.GetMax())
            maxRecord = curRecord;
    }

    maxRecord.show(nums);

    return 0;
}

#define  ArraySize(array)       ( sizeof(array) / sizeof( array[0] ) )

int main(int argc, char **argv)
{
    {
        int nums[] = {-2, 5, 3, -6, 4, -8, 6};
        MaxArray(nums, nums + ArraySize(nums));
    }
    {
        int nums[] = {1, -2, 3, 10, -4, 7, 2, -5};
        MaxArray(nums, nums + ArraySize(nums));
    }
}
